class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int len = s.size();
        if(len == 0) return false;
        set<int> tmp;

        for(int i = 0; i < len; ++i) {
            if(wordDict.find(s.substr(0,i + 1)) != wordDict.end()) {
                tmp.insert(i);
                continue;
            }
            for(set<int>::iterator it = tmp.begin(); it != tmp.end(); ++it) {
                if(wordDict.find(s.substr((*it) + 1, i - (*it))) != wordDict.end()) {
                    tmp.insert(i);
                    break;
                }
            }
        }
        if(tmp.find(len - 1) != tmp.end()) return true;
        else return false;
    }
};